package 中等.数学;

/**
 * 给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，
 * 并返回按位或能得到最大值的 不同非空子集的数目 。
 * 如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a
 * 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
 * 对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets
 */
public class 统计按位或能得到最大值的子集数目_2044 {

    public static void main(String[] args) {

        int[] nums = {3, 1};
        System.out.println(countMaxOrSubsets(nums));

    }

    /**
     * 1 <= nums.length <= 16
     * 暴力不行，子集数量达到了2的16次方-1
     * 找规律：
     * 按位或任意正数都不会减少，那么我们直接找数组的最大值集合，得到以最大值开头，或者结尾的子集
     * 求子集：
     * 位运算，每一个元素都有选和不选两种可能，子集必须有一个元素，排除掉全部不选的可能，
     * 那么子集的数量是2的n次方-1，可以用bit位来对应两种可能，1代表选择，0代表不选
     *
     * @param nums
     * @return
     */
    public static int countMaxOrSubsets(int[] nums) {
        // 这里减去1之后，最大值得bit最左边到最右边距离，正常是nums.length的长度，2的1次方(1 0)->1(0 1)，2的2次方(1 0 0)->3(1 1)
        int maxZiCount = (1 << nums.length) - 1;  // -的运算优先级比位运算高
        int maxOrValue = 0;
        int ans = 0;
        for (int curZi = 1; curZi <= maxZiCount; curZi++) {
            int curOrValue = 0;  //初始值0与其他数|不变
            // 需要求出当前数字的第1-num.length的所有bit位，是1还是0
            for (int i = 0; i < nums.length; i++) {
                // 1的bit位情况 ... 0 0 1 ,那么子集的数字与 & 1 之后 = 1，第一位是1
                if (((curZi >> i) & 1) == 1) {
                    curOrValue |= nums[i];
                }
            }
            if (curOrValue > maxOrValue) {
                ans = 0;
                ans++;
                maxOrValue = curOrValue;
            } else if (curOrValue == maxOrValue) {
                ans++;
            }
        }
        return ans;
    }

}
